package Sequence;

public class Test0583 {
    public static void main(String[] args) {
        String word1 = "sea";
        String word2 = "eat";

        Solution0583_1 solution0583_1 = new Solution0583_1();
        int result = solution0583_1.minDistance(word1, word2);
        System.out.println(result);
    }
}

class Solution0583_1 {
    public int minDistance(String word1, String word2) {
        char[] charArray1 = word1.toCharArray();
        char[] charArray2 = word2.toCharArray();

        int length1 = charArray1.length;
        int length2 = charArray2.length;

        int[] dp1 = new int[length2 + 1];
        int[] dp2 = new int[length2 + 1];

        for (char c1 : charArray1) {
            for (int i = 0; i < length2; i++) {
                char c2 = charArray2[i];

                dp2[i + 1] =(c1 == c2)? dp1[i]+1:
                        Math.max(dp1[i+1], dp2[i]);

            }
            int[] temp = dp1;
            dp1 = dp2;
            dp2 = temp;
        }

        return length2+length1-dp1[length2]*2;
    }
}
